package traverser;

/**
 * LinkProcessor.java
 * Library of utilities for dealing with a Wikipedia page.
 * 
 * LinkProcessor should be instantiated for each page that you want to process.  The
 * 	constructor pulls the HTML down from the web and strips the links out of it, storing
 * 	them for later use.
 * 
 * There are 3 big methods here: removeDups, sort and shuffle.
 * 	removeDups ensures that each link is unique
 * 	sort sorts the links alphabetically
 * 	knuthShuffle puts the links into random order
 * 
 * Written by:
 * 	Tim Krull (constructor)
 * 	John Moore (sort)
 * 	Dan Roberts (removeDups, knuthShuffle)
 * 
 * Last modified 9/26
 */

import java.io.InputStream;
import java.net.URL;
import java.util.*;

public class LinkProcessor {

	private String htmlCode; // HTML code of the website
	private String[] links; // LinkedList of all of the links on the given
							// webpage

	// Timers for various functions
	private static long HTMLtime = 0;
	private static long extractTime = 0;
	private static long processTime = 0;

	public LinkProcessor(String website) {
		// Record how long stuff takes
		long startTime, endTime;

		startTime = System.currentTimeMillis();
		getHTML(website);
		endTime = System.currentTimeMillis();
		HTMLtime += endTime - startTime;

		startTime = System.currentTimeMillis();
		extractLinks(htmlCode);
		endTime = System.currentTimeMillis();
		extractTime += endTime - startTime;
	}

	// main function - runs all of the functions and then returns the sorted
	// LinkedList of links
	public String[] getList() {
		return links;
	}

	// How many links are there?
	public int count() {
		return links.length;
	}

	// gets HTML code from website and puts it in htmlCode
	public void getHTML(String website) {
		URL site = null;
		InputStream contentStream = null;
		try {
			site = new URL(website);
			contentStream = site.openStream();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(0);
		}

		Scanner sc = new Scanner(contentStream);
		while (sc.hasNext()) {
			htmlCode += sc.nextLine();
		}
	}

	// Extracts the links from a piece of HTML and puts them into an array
	public void extractLinks(String htmlCode) {
		String key = "<a href=\"/wiki/"; // the term we are searching for
		int keyLen = key.length();
		String link = "";

		int index = 0; // index of the search
		int start = 0; // start index of the link
		int end = 0; // end index of the link

		// Use an array list for simple implementation
		ArrayList<String> list = new ArrayList<String>();

		// runs while index is less than string length
		while (index < htmlCode.length()) {
			// searches for key terms and gets index
			start = htmlCode.indexOf(key, index);
			// if key terms found, add them to the list and update index
			if (start > 0) {
				end = htmlCode.indexOf("\"", start + keyLen);
				link = htmlCode.substring(start + keyLen, end);
				if ((link.contains("Wikipedia:"))
						|| (link.contains("Special:"))
						|| (link.contains("Help:")) || (link.contains("File:"))
						|| (link.contains("Category:"))
						|| (link.contains("Template:"))) {
					index = end;
					continue;
				}
				list.add("http://en.wikipedia.org/wiki/" + link);
				index = end;
			}
			// if key terms not found, end loop
			else if (start == -1) {
				break;
			}
		}

		// Cast from ArrayList to array is super easy.
		this.links = new String[list.size()];
		this.links = list.toArray(this.links);
	}

	// Remove duplicate entries from links
	public void removeDuplicates() {
		int count = links.length;
		for (int i = 0; i < count; i++) {
			for (int j = i + 1; j < count; j++) {
				if (links[i].equals(links[j])) {
					count--; // One fewer unique link
					links[j] = links[count]; // Omit the duplicate link, draw a
												// new one from the end
					j--; // Check the just swapped in link
				}
			}
		}
		String[] noDups = new String[count];
		for (int i = 0; i < count; i++) {
			noDups[i] = links[i];
		}
		links = noDups;
	}

	// sorts linkArray - removes duplicates and then puts into alpha order
	public void sort() {
		ListSorter linkSort = new ListSorter(links);
		links = linkSort.sort();
	}

	// Put the links into a random order
	public void knuthShuffle() {
		for (int i = 0; i < links.length - 1; i++) {
			int j = i + (int) (Math.random() * (links.length - i - 1));
			String temp = links[i];
			links[i] = links[j];
			links[j] = temp;
		}
	}

	// Metrics
	public static long getHTMLtime() {
		return HTMLtime;
	}

	public static long getExtractTime() {
		return extractTime;
	}

	public static long getProcessTime() {
		return processTime;
	}

	public static void printMetrics() {
		System.out.println("Time cost breakdown:");
		System.out.println("Time spent on HTML:\t" + HTMLtime);
		System.out.println("Time spent on extract:\t" + extractTime);
		System.out.println("Time spent on process:\t" + processTime);
	}

	// nested class
	class ListSorter {

		String[] data;
		String[] newData;
		private int number;

		// constructor
		public ListSorter(String[] data) {
			this.data = data;
		}

		// sorts the list/array
		public String[] sort() {
			this.newData = removeDuplicates();

			data = null;
			number = newData.length;

			mergesort(0, number - 1);

			return newData;
		}

		public String[] removeDuplicates() {
			List<String> list = Arrays.asList(data);
			Set<String> set = new HashSet<String>(list);

			String[] result = new String[set.size()];
			set.toArray(result);
			return result;
		}

		private void mergesort(int low, int high) {
			// Check if low is smaller then high, if not then the array is
			// sorted
			if (low < high) {
				// Get the index of the element which is in the middle
				int middle = (low + high) / 2;
				// Sort the left side of the array
				mergesort(low, middle);
				// Sort the right side of the array
				mergesort(middle + 1, high);
				// Combine them both
				merge(low, middle, high);
			}
		}

		private void merge(int low, int middle, int high) {

			// Helperarray
			String[] helper = new String[number];

			// Copy both parts into the helper array
			for (int i = low; i <= high; i++) {
				helper[i] = newData[i];
			}

			int i = low;
			int j = middle + 1;
			int k = low;
			// Copy the smallest values from either the left or the right side
			// back
			// to the original array
			while (i <= middle && j <= high) {
				if (helper[i].compareTo(helper[j]) < 0) {
					newData[k] = helper[i];
					i++;
				} else {
					newData[k] = helper[j];
					j++;
				}
				k++;
			}
			// Copy the rest of the left side of the array into the target array
			while (i <= middle) {
				newData[k] = helper[i];
				k++;
				i++;
			}
			helper = null;

		}
	}

}
